package com.example.demo.suanfa_2tree;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 树结构 序列化 和 反序列化
 */
public class SerializeAndReconstructTreeDemo {

    class Node {
        String value;
        Node left;
        Node right;

        public Node(String value) {
            this.value = value;
        }
    }

    /**
     * 先序 序列化
     *
     * @param head
     * @return
     */
    public Queue<String> inSerial(Node head) {
        Queue stack = new LinkedList();
        preSerial(head, stack);
        return stack;
    }

    public void preSerial(Node node, Queue stack) {
        if (node == null) {
            stack.add(null);
            return;
        }
        stack.add(node.value);
        preSerial(node.left, stack);
        preSerial(node.right, stack);
    }

    public Node desc(Queue<String> queue) {
        if (queue == null || queue.isEmpty()) {
            return null;
        }
        return preDesc(queue);
    }

    public Node preDesc(Queue<String> queue) {
        if (!queue.isEmpty()) {
            String poll = queue.poll();
            if (poll == null) {
                return null;
            }
            Node pollNode = new Node(poll);
            pollNode.left = preDesc(queue);
            pollNode.right = preDesc(queue);
            return pollNode;
        }
        return null;
    }

    /**
     * 层序 序列化
     *
     * @param head
     * @return
     */
    public Queue<String> levelSerial(Node head) {
        Queue<String> ans = new LinkedList();
        if (head == null) {
            ans.add(null);
        } else {
            Queue<Node> queue = new LinkedList();
            queue.add(head);
            ans.add(head.value);
            while (!queue.isEmpty()) {
                Node poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                    ans.add(poll.left.value);
                } else {
                    ans.add(null);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                    ans.add(poll.right.value);
                } else {
                    ans.add(null);
                }
            }
        }
        return ans;
    }

    public Node buildByLevelQueue(Queue<String> queue) {
        if (queue != null || !queue.isEmpty()) {
            String poll = queue.poll();
            Queue<Node> ans = new LinkedList<>();
            Node head = new Node(poll);
            ans.add(head);
            if (head == null){
                return null;
            }

            while (!ans.isEmpty()) {
                Node poll1 = ans.poll();
                if (poll1 != null){
                    Node pollLeft = generateNode(queue.poll());
                    poll1.left = pollLeft;
                    Node pollRight = generateNode(queue.poll());
                    poll1.right = pollRight;

                    if (pollLeft!=null){
                        ans.add(pollLeft);
                    }
                    if (pollRight!=null){
                        ans.add(pollRight);
                    }
                }
            }
            return head;
        }
        return null;
    }

    public Node generateNode(String str){
        if (str==null){
            return null;
        }
        return new Node(str);
    }

}
